#ifndef	__BFX__ARRAY_H__
#define	__BFX__ARRAY_H__

// requires for replacement new.
#if defined(_WIN32) || defined(__CYGWIN__)
#include <new>
#endif

namespace BFX
{

template <typename T>
class Array
{
	typedef	T	TYPE;
	typedef	const T&	ARG_TYPE;

public:
	// Initializes array with given capacity.
	Array(int nCapacity = 16)
		: m_pData(NULL), m_nSize(0), m_nAllocSize(0)
	{
		BFX_REQUIRE(nCapacity >= 0);

		Capacity(nCapacity);
	}
	virtual ~Array()
	{
		Clear();
	}

	// Inserts a given element at the end of the array.
	void Add(ARG_TYPE value)
	{
		Capacity(m_nSize + 1);
		m_pData[m_nSize++] = value;

	}
	// Adds the elements in another given array to the end of the current array.
	void AddFromArray(Array* pSrcArray)
	{
		if (pSrcArray == NULL)
			return;

		int nSrcSize = pSrcArray->GetSize();
		if (nSrcSize == 0)
			return;

		Capacity(m_nSize + nSrcSize);
		for (int i = 0; i < nSrcSize; i++)
		{
			m_pData[m_nSize + i] = pSrcArray->GetAt(i);
		}
		m_nSize += nSrcSize;
	}
	// Inserts a given element into the array at a given index.
	void InsertAt(int iIndex, ARG_TYPE value)
	{
		BFX_REQUIRE(iIndex >= 0 && iIndex <= m_nSize);

		// grow-up the array if necessary.
		Capacity(m_nSize + 1);
		if (iIndex < m_nSize)
		{
			// inserting in the middle of the array

			// shift old data up to fill gap
			memmove(m_pData + iIndex + 1, m_pData + iIndex, (m_nSize - iIndex) * sizeof(TYPE));

			// re-init slots we copied from
			::new ((void*) (m_pData + iIndex)) TYPE;
		}
		else
			; // adding after the end of the array

		// insert new value in the gap
		m_pData[iIndex] = value;
		m_nSize++;
	}
	// Removes the element at index.
	void RemoveAt(int iIndex)
	{
		BFX_REQUIRE(iIndex >= 0 && iIndex < m_nSize);

		// destroy the data.
		(m_pData + iIndex)->~TYPE();

		if (iIndex < (m_nSize - 1))
		{
			// shift old data down
			memmove(m_pData + iIndex, m_pData + iIndex + 1, (m_nSize - iIndex - 1) * sizeof(TYPE));
		}
		m_nSize--;
	}
	// Removes all occurrences in the array of a given element.
	void Remove(ARG_TYPE value)
	{
		int iIndex;
		while ((iIndex = Find(value)) == -1)
		{
			RemoveAt(iIndex);
		}
	}
	void Clear()
	{
		if (m_pData == NULL)
			return;

		for (int i = 0; i < m_nSize; i ++)
			(m_pData + i)->~TYPE();
		delete[] (BYTE*)m_pData;
		m_pData = NULL;
		m_nSize = m_nAllocSize = 0;
	}

	ARG_TYPE operator[](int iIndex) const
	{
		BFX_REQUIRE(iIndex < m_nSize);
		return m_pData[iIndex];
	}

	TYPE& operator[](int iIndex)
	{
		BFX_REQUIRE(iIndex < m_nSize);
		return m_pData[iIndex];
	}

	// Returns the element located at index.
	ARG_TYPE GetAt(int iIndex) const
	{
		BFX_REQUIRE(iIndex < m_nSize);
		return m_pData[iIndex];
	}
	// Returns the lowest index whose corresponding array value is equal to a given element.
	int Find(ARG_TYPE value) const
	{
		if (m_nSize > 0)
		{
			BFX_ENSURE(m_pData != NULL);

			for (int i = 0; i < m_nSize; i++)
			{
				if (m_pData[i] == value)
					return i;
			}
		}
		return -1;
	}
	bool Contains(ARG_TYPE value) const
	{
		return (Find(value) != -1);
	}
	// Returns the number of elements currently in the array.
	int GetSize() const
	{
		return m_nSize;
	}

	void Capacity(int nCapacity)
	{
		BFX_ASSERT(nCapacity >= 0);

		if (nCapacity == 0)
			return;

		// calculate required buffer length, align by m_nAllocSize.
		int nAllocSize = __MAX(m_nAllocSize, 2);
		while (nAllocSize < nCapacity)
		{
			nAllocSize *= 2;
		}
		// allocate new block if necessary.
		if (nAllocSize > m_nAllocSize)
		{
			TYPE* pNewData = (TYPE*)new BYTE[nAllocSize * sizeof(TYPE)];

			// copy exist elements to new block.
			memmove(pNewData, m_pData, m_nSize * sizeof(TYPE));

			// construct remaining elements
			for (int i = 0; i < (nAllocSize - m_nSize); i++)
				::new ((void*) (pNewData + m_nSize + i)) TYPE;

			// releases old stuff (note: no destructors called)
			if (m_pData != NULL)
				delete[] (BYTE*) m_pData;

			m_pData = pNewData;
			m_nAllocSize = nAllocSize;
		}
	}

private:
	TYPE*	m_pData;
	int	m_nSize;
	int	m_nAllocSize;
};

};	//	namespace BFX

#endif	//	__BFX__ARRAY_H__
